package Sorters;

public class MergeSort implements DataSorter<Integer> {
    //TODO: code indentation missing, implement class logging using log4j

    @Override
    public Integer[] sort(final Integer[] massive) {
        if (massive == null) {
            return null;
        }
        if (massive.length == 0) {
            return massive;
        }
        Integer[] array = new Integer[massive.length];
        System.arraycopy(massive, 0, array, 0, massive.length);
        mergeSort(array, 0, massive.length - 1);
        return array;

    }

    private void mergeSort(Integer[] massive, int left, int right) {
        if (right <= left) {
            return;
        }
        int mid = (left + (right - left) / 2);
        mergeSort(massive, left, mid);
        mergeSort(massive, mid + 1, right);
        merge(massive, left, mid, right);
    }

    private void merge(Integer[] massive, int low, int mid, int hi) {
        int i = low;
        int j = mid + 1;
        Integer[] array = new Integer[massive.length];
        for (int k = 0; k <= hi; k++) {
            array[k] = massive[k];
        }
        for (int k = low; k <= hi; k++) {
            if (i > mid) {
                massive[k] = array[j++];
            } else if (j > hi) {
                massive[k] = array[i++];
            } else if (array[j] < (array[i])) {
                massive[k] = array[j++];
            } else {
                massive[k] = array[i++];
            }
        }
    }
}
